package com.fengdi.everyday.middle;

/**
 * @Description 2654 使数组元素全部变为1的最小操作次数
 * @Date 09:45
 */
public class MinOperations {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int g = 0;
        int num1 = 0;

        for(int num : nums) {
            if(num == 1) {
                num1++;
            }
            g = this.gcb(g, num);
        }

        if(num1 > 1) {
            return n - num1;
        }

        if(g > 1) {
            return -1;
        }

        int minLen = n;
        for(int i = 0; i < n; i++) {
            int currentGcb = 0;
            for(int j = i; j < n; j++) {
                currentGcb = this.gcb(currentGcb, nums[j]);
                if(currentGcb == 1) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }

        return minLen + n - 2;
    }


    // 辗转相除法
    private int gcb(int x, int y) {
        while(y != 0) {
            int tmp = y;
            y = x % y;
            x = tmp;
        }
        return x;
    }
}
